using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.IO;

namespace KiemBao
{
    class CacThuatToan
    {
        public static void BFSChiPhiThapNhat(ArrayList _V0, ArrayList _arrkhoitaoDuongDiNganNhat, ArrayList _S, ArrayList _Q)
        {
            _V0 = _S;
            foreach (Node khoitao in _V0)
            {
                khoitao.PREVIOUS = null;
                khoitao.G = 0.0;
                khoitao.LABEL = 0;
            }
            _arrkhoitaoDuongDiNganNhat.Add(_V0);
            int num = 0;
            bool flag = false;
            while (!flag)
            {
                ArrayList list = new ArrayList();
                ArrayList list2 = new ArrayList();
                list2.Clear();
                list.Clear();
                list2 = (ArrayList)_arrkhoitaoDuongDiNganNhat[num];
                if (list2.Count == 0)
                {
                    flag = true;
                }
                else
                {
                    foreach (Node khoitao2 in list2)
                    {
                        ArrayList list3 = new ArrayList();
                        foreach (string str in khoitao2.SUCCESS)
                        {
                            foreach (Node khoitao3 in _Q)
                            {
                                if (str == khoitao3.NAME)
                                {
                                    list3.Add(khoitao3);
                                }
                            }
                        }
                        foreach (Node khoitao4 in list3)
                        {
                            if ((khoitao4.LABEL < 0) || ((khoitao2.G + khoitao2.Cost(khoitao4)) < khoitao4.G))
                            {
                                khoitao4.PREVIOUS = khoitao2;
                                khoitao4.LABEL = num + 1;
                                khoitao4.G = khoitao2.G + khoitao2.Cost(khoitao4);
                                list.Add(khoitao4);
                            }
                        }
                    }
                }
                _arrkhoitaoDuongDiNganNhat.Add(list);
                num++;
            }
        }
        public static void BFS_ChiPhiThapNhat(ArrayList _V0, ArrayList _arrStateDuongDiNganNhat, ArrayList _S, ArrayList _Q, ArrayList _G)
        {
            _V0 = _S;
            foreach (Node state in _V0)
            {
                state.PREVIOUS = null;
                state.LABEL = 0;
            }
            _arrStateDuongDiNganNhat.Add(_V0);
            int num = 0;
            bool flag = false;
            while (!flag)
            {
                ArrayList list = new ArrayList();
                ArrayList list2 = new ArrayList();
                list2.Clear();
                list.Clear();
                list2 = (ArrayList)_arrStateDuongDiNganNhat[num];
                bool flag2 = false;
                for (int i = 0; i < list2.Count; i++)
                {
                    if (((Node)_G[0]).NAME == ((Node)list2[i]).NAME)
                    {
                        flag2 = true;
                    }
                }
                if ((list2.Count == 0) && !flag2)
                {
                    flag = true;
                }
                else
                {
                    foreach (Node state2 in list2)
                    {
                        ArrayList list3 = new ArrayList();
                        foreach (string str in state2.SUCCESS)
                        {
                            foreach (Node state3 in _Q)
                            {
                                if (str == state3.NAME)
                                {
                                    list3.Add(state3);
                                }
                            }
                        }
                        foreach (Node state4 in list3)
                        {
                            if (state4.LABEL < 0)
                            {
                                state4.PREVIOUS = state2;
                                state4.LABEL = num + 1;
                                list.Add(state4);
                            }
                        }
                    }
                }
                _arrStateDuongDiNganNhat.Add(list);
                num++;
            }
        }
        public static void DFS(Node Start, ArrayList _Q, ArrayList _G)
        {
            ArrayList list = new ArrayList();
            foreach (string str in Start.SUCCESS)
            {
                foreach (Node state in _Q)
                {
                    if (str == state.NAME)
                    {
                        list.Add(state);
                    }
                }
            }
            Start.LABEL = 1;
            foreach (Node state2 in list)
            {
                if (Start.NAME == ((Node)_G[0]).NAME)
                {
                    break;
                }
                if (state2.LABEL < 0)
                {
                    state2.PREVIOUS = Start;
                    DFS(state2, _Q, _G);
                }
            }
        }














    }
}
